package com.gjh.study.algorithm4.sort;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Stopwatch;

public class SortBase {

    public void sort(Comparable[] a) {
    }

    public static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    public static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }

    public static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        // test1();
        // test2();
        // test3();
        // test4();
        // test5();
        test6();
    }

        public static void test6() {
        char[] chars = "QUICKSORTEXAMPLE".toCharArray();
        String[] a = new String[chars.length];
        for (int i = 0; i < chars.length; i++) {
            a[i] = String.valueOf(chars[i]);
        }
        new Quick().sort(a);
        assert isSorted(a);
        show(a);
    }

    public static void test5() {
        char[] chars = "MERGESORTEXAMPLE".toCharArray();
        String[] a = new String[chars.length];
        for (int i = 0; i < chars.length; i++) {
            a[i] = String.valueOf(chars[i]);
        }
        // new Merge().sort(a);
        new MergeBU().sort(a);
        assert isSorted(a);
        show(a);
    }

    public static void test2() {
        char[] chars = "SHELLSORTEXAMPLE".toCharArray();
        String[] a = new String[chars.length];
        for (int i = 0; i < chars.length; i++) {
            a[i] = String.valueOf(chars[i]);
        }
        new Shell().sort(a);
        assert isSorted(a);
        show(a);
    }

    public static void test3() {
        int N = 1000000;
        Double[] b = randomDouble(N);
        double t2 = time(new Shell(), b);
        StdOut.printf("Shell time: %.6f", t2);
    }

    public static void test4() {
        int N = 1000000;
        Double[] b = randomDouble(N);
        double t2 = time(new Insertion(), b);
        StdOut.printf("Insertion time: %.6f", t2);
    }

    public static void test1() {
        int N = 10000;
        Double[] a = randomDouble(N);
        Double[] b = randomDouble(N);

        double t1 = time(new Insertion(), a);
        double t2 = time(new Selection(), b);
        StdOut.printf("Insertion is %.6f times faster than Selection.", t1 / t2);
    }

    public static Double[] randomDouble(int N) {
        Double[] a = new Double[N];
        for (int i = 0; i < N; i++) {
            a[i] = StdRandom.uniform();
        }
        return a;
    }

    public static double time(SortBase s, Comparable[] a) {
        Stopwatch timer = new Stopwatch();
        s.sort(a);
        return timer.elapsedTime();
    }
}
